LeetCode 50. Pow(x,n)

题意

Implement pow(x, n).
实现幂乘函数Pow(x,n)。

思路

快速幂运算：

求x的n次方，朴素迭代需要O(n)的复杂度，但当n为整数时可以用倍乘的思想将复杂度简化为log(n)。

该算法思想借鉴与于二进制数转十进制数的算法，例如 Pow(1.3,11)权值和位值分别为：

权值  8  4  2  1
位值  1  0  1  1

用一个变量 p 维护权值，每次迭代 p *= p 来维护，当位为1时将 p 乘入结果。

需要注意的地方

1. 输入的指数为-2147483648时，在int里把-2147483648转化为正仍为-2147483648。

2. 提交为C语言可能会遇到 1.0/0.0 = 1.0 的情况，而正确结果应该是inf，提交为C++可得inf。

代码

class Solution {
public:
    double myPow(double x, int n) {
        if(x == 0)
        {
            if(n == 0) return 1.0;
            return 0;
        }
        if(n < 0)
        {
            x = 1.0 / x;
        }
        long long p = abs((long long)n);
        double ret = 1.0;
        while(p > 0)
        {
            if(p & 1)
            {
                ret *= x;
            }
            x *= x;
            p >>= 1;
        }
        return ret;
    }
};